package lab2.datastructures;

import lab2.testSortCol.CollectionWithGet;
/**
 * An implementation of a splaytree, which is built
 * upon an extenstion of a binary search tree.
 * Still its not a complete splaytree since the
 * tree itself doesnt splay on insertion and deletion,
 * only when searching.
 * 
 * @author Anders & Joanna
 *
 * @param <E> needs to implement comparable interface
 */
public class SplayTreeWithGet<E extends Comparable<? super E>> 
	   extends BinarySearchTree<E>
	   implements CollectionWithGet<E>{
	
	
	@Override
	public Entry find(E elem, Entry t){
		if ( t == null ){
			return null;
		}   
	    else{
		    int jfr = elem.compareTo( t.element );
			if ( jfr  < 0 ){
				if(t.left == null){
					splay(t);
					return null;
				}
				else{
					return find( elem, t.left );
				}
			}
			else if ( jfr > 0 ){
				if(t.right == null){
					splay(t);
					return null;
				}
				else{
					return find( elem, t.right );
				}
				
			}
			else{
				splay(t);
				return root;
			}
			
	    }
	}


	/**
	 * Splay
	 * 
	 * Description: Move the element of entry forwards to root,
	 * and rotates the nodes according to there relations.
	 * 
	 * @param Entry entry the node to splay(move to root)
	 */
	private void splay(Entry entry){			
		//Is root?
		if(entry.parent != null){
			if(entry.parent.parent ==null){
				if(entry.parent.left == entry){
					rotateZag(entry.parent);		
				}
				else {
					rotateZig(entry.parent);
				}
			}
			else{
				if(entry.parent.parent.left == entry.parent){
					if(entry.parent.left == entry){
						Entry temp = entry.parent.parent;
						rotateZagZag(temp);
						splay(temp);
					}
					else{
						Entry temp = entry.parent.parent;
						rotateZagZig(temp);	
						//rotateZagZig2(entry);	
						splay(temp);
					}
				}
				else if(entry.parent.parent.right == entry.parent){
					if(entry.parent.right == entry){
						Entry temp = entry.parent.parent;
						rotateZigZig(temp);
						splay(temp);
					}
					else{
						Entry temp = entry.parent.parent;
						rotateZigZag(temp);		
						//rotateZigZag2(entry);		
						splay(temp);
					}
				}
			}
		}
	}
	
	
    /* Rotera 1 steg i h�gervarv, dvs 
    x'                 y'
   / \                / \
  y'  C   -->        A   x'
 / \                    / \  
A   B                  B   C
*/
	
	/**
	 * Zag
	 * 
	 * Description: Rotates right, but have leftchild from node
	 */
	private void rotateZag(Entry x) {
		Entry y = x.left;
		E temp =  x.element;
		x.element = y.element;
		y.element = temp;
		x.left = y.left;
		if (x.left != null)
			x.left.parent = x;
		y.left = y.right;
		y.right = x.right;
		if (y.right != null)
			y.right.parent = y;
		x.right = y;
	} // rotateRight
	
    /* Rotera 1 steg i v�nstervarv, dvs 
    x'                 y'
   / \                / \
  A   y'  -->        x'  C
     / \            / \  
    B   C          A   B   
*/
	/**
	 * Zig
	 * 
	 * Description: Rotates left, but have rightchild from node
	 */
	private void rotateZig(Entry x) {
		Entry y = x.right;
		E temp = x.element;
		x.element = y.element;
		y.element = temp;
		x.right = y.right;
		if (x.right != null)
			x.right.parent = x;
		y.right = y.left;
		y.left = x.left;
		if (y.left != null)
			y.left.parent = y;
		x.left = y;

	} // rotateLeft

    /*
	  z'   				    x'   
	 / \  				   / \ 
    A   y'  ---->         y'  D 
	   / \  			 / \  
	  B   x'			z'  C 
		 / \		   / \  	
	    C   D	      A   B  
*/
	/**
	 * ZigZig
	 * 
	 * Description: Rotates left, but have rightchild as rightchild from node.
	 * The target element is lifted up by two levels.
	 * 
	 * @param Entry x the node which element is lifted up 
	 */
	private void rotateZigZig(Entry x) {		
		Entry y = x.right;
		Entry z = x.right.right;
		
		//Childs
		Entry xLeft = x.left;
		Entry yleft = y.left;
		Entry zLeft = z.left;
		Entry zright = z.right;
		
		//Elementswap
		E e = x.element;
		x.element = z.element;
		z.element = e;
		
		//X
		x.left = y;
		x.right = zright;
		
		if(zright !=null){
			zright.parent = x;
		}
		
		//Y
		y.left = z;
		y.right = zLeft;
		
		if(zLeft != null){
			zLeft.parent = y;
		}
		
		//Z
		z.left = xLeft;
		z.right = yleft;

		if(xLeft != null){
			xLeft.parent = z;
		}
		if(yleft != null){
			yleft.parent = z;
		}
	} 
	
    /*
	    z'                  x'   
	   / \                 / \  
	  y'  D   -->         A   y'
	 / \                	 / \
	x'  C                   B   z'
   / \  					   / \
  A   B  					  C   D
	*/
	/**
	 * ZagZag
	 * 
	 * Description: Rotates right, but have leftchild as leftchild from node.
	 * The target element is lifted up by two levels.
	 * 
	 * @param Entry x the node which element is lifted up 
	 */
	private void rotateZagZag(Entry x) {
		Entry y = x.left;
		Entry z = x.left.left;
		
		//Childs
		Entry xRight = x.right;
		Entry yRight = y.right;
		Entry zRight = z.right;
		Entry zLeft = z.left;
		
		//Elementswap
		E e = x.element;
		x.element = z.element;
		z.element = e;
		
		//X
		x.right = y;
		x.left = zLeft;
		
		if(zLeft !=null){
			zLeft.parent = x;
		}
		
		//Y
		y.right = z;
		y.left = zRight;
		
		if(zRight != null){
			zRight.parent = y;
		}
		
		//Z
		z.right = xRight;
		z.left = yRight;

		if(xRight != null){
			xRight.parent = z;
		}
		if(yRight != null){
			yRight.parent = z;
		}
	} 

    /* Rotera 2 steg i h�gervarv, dvs 
    x'                  z'
   / \                /   \
  y'  D   -->        y'    x'
 / \                / \   / \
A   z'             A   B C   D
   / \  
  B   C  
*/
	/**
	 * ZagZig
	 * 
	 * Description: Rotates left, but have rightchild as lefttchild from node
	 */
	private void rotateZagZig(Entry x) {
		Entry y = x.left, z = x.left.right;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.right = z.left;
		if (y.right != null)
			y.right.parent = y;
		z.left = z.right;
		z.right = x.right;
		if (z.right != null)
			z.right.parent = z;
		x.right = z;
		z.parent = x;
	} // doubleRotateRight

	   /* Rotera 2 steg i v�nstervarv, dvs 
    x'                  z'
   / \                /   \
  A   y'   -->       x'    y'
     / \            / \   / \
    z   D          A   B C   D
   / \  
  B   C  
*/
	/**
	 * ZigZag
	 * 
	 * Description: Rotates left, but have leftchild as rightchild from node
	 */
	private void rotateZigZag(Entry x) {
		Entry y = x.right, z = x.right.left;
		E e = x.element;
		x.element = z.element;
		z.element = e;
		y.left = z.right;
		if (y.left != null)
			y.left.parent = y;
		z.right = z.left;
		z.left = x.left;
		if (z.left != null)
			z.left.parent = z;
		x.left = z;
		z.parent = x;
	} // doubleRotateLeft

	@Override
	public E get(E e) {
		Entry entry = find(e,root);
		return entry == null ? null : entry.element;
	}
}
